A method and an apparatus for performing hierarchical address translation, and especially a method and an apparatus for receiving a destination address and generating an address of a next hop router, using a content addressable memory, a fast memory module and a memory module.
Internet routers receive data packets containing destination addresses, perform an address translation and forward the data packets according to result of the address translation process. The product of the address translation process is an address of the next hop router.
Usually, the destination address has a hierarchical structure. A hierarchical address has an internal structure that can be used in protocol processing of the address. Hierarchical addresses are used in a variety of internet protocols such as IPv6 and IPv4.
Forwarding data packets involve address lookup in a routing database. Various methods and devices for performing forwarding packets are described at U.S. Pat. No. 5,920,886 of Feldmeier, U.S. Pat. No. 5,938,736 of Muller et al, U.S. Pat. No. 5,917,821 of Gobuyan et al and U.S. Pat. No. 5,953,312 of Crawley et al.
Usually, a routing database does not include all the possible destination addresses, but has a plurality of address prefixes, each representing a group of destination addresses reachable through the same interface. The prefixes are of variable length, and a packet should be forwarded to a selected group, a selected group being a group of destination addresses that are represented by the most specific prefix/the longest prefix that matches the destination address of the data packet. xe2x80x9cIP Lookups using Multiway and Multicolon Searchxe2x80x9d by B. Lampson, V. Srinivasan and G. Varghese, (i.e.xe2x80x94Lampson et. al.) describes a device and a method for performing address lookups. According to the method a trinary prefix that has xe2x80x9cdon""t care xe2x80x9d bits is encoded to two fixed length binary strings, these two strings represent a start and an end of a binary range. For example, a trinary prefix 11101* * * having three xe2x80x9cdon""t carexe2x80x9d bits is encoded to the following binary strings: 11101000 and 11101111.
All of the strings are sorted and form a first array of fixed length strings. Then, a binary search is done in order to find a best-matched string. The best-matched string is either a string that exactly matches the destination address a string that represents a start of a narrowest enclosing range between two strings encoded from a single prefix, in which the destination address falls.
Two pointers are used for each entry in the first array. A first pointer points to a string that exactly matches the destination address. A second pointer points to a string that is associated to a narrowest enclosing range that matches the destination address, when there is no exactly matching string.
For example, assuming that an string is 6 bits wide, three trinary prefixes 1*, 101* and 10101* are translated to 1*****, 101*** and 10101*, to be further converted to the following binary strings: 111111, 100000, 101111, 101000, 101011 and 101010, referred to as S1, S2, S3, S4, S5 and S6 accordingly. 1* is associated with a first pointer p1, 101* is associated with a second pointer p2, 10101* is associated with a third pointer p3. Each binary string is associated with a pointer that is provided when it matches the destination address and a second pointer that is provided when there is not such an exact match. S6 is associated with p1, S5 is associated with p2 and p1, S4 is associated with p2 and p3, S3 is associated with p3, S2 is associated with p2 and S1 is associated with p1.
Using two pointers for each entry is relatively memory consuming. A first portion of the first array and the accompanying pointers can be stored in a cache memory; the remaining sorted strings of the first array are stored in a relative slow external memory module. During a binary search a destination address is compared to the strings of the first portion of the first array and either a first intermediate best-matched string or a matched string are generated. Usually some iterations are required and at least a portion of the remaining sorted strings are written to the cache. The result of the last search iteration is a best-matched string, pointing to the next hop router. Usually a last level of the first array comprises of a plurality of leafs in which the next hop IDs are stored. Because two pointers are associated to each entry there is a need of many leafs.
Lampson et al. suggest partitioning the single binary search into multiple binary search tables for each value of a first Y bits. A first front-end array will store 2Y best matching prefixes for the first Y bits. The I""th memory location of the first end array stores the best matching prefix of I.
Lampson et al. Further suggests to perform a multiway search instead of a binary search. A multiway search is characterized by two or more keys per node. The multiway search technique exploits the fact that most processors prefetch an entire cache line when performing a memory access and that such an entire line can store more than two strings. They further suggest performing a multicolumn search in which each string is partitioned into a plurality of columns, starting with the most significant bits of the string. A binary search is performed in each column until a match is found. After such a match is found the next columns that are associated to the prior matched columns are searched.
There is a need of an improved method and apparatus for performing a hierarchical address translation. Especially there is a need for a method and a device that are fast and are cost effective. Furthermore, there is a need of a method and device for translating a hierarchical address that consume less memory space than prior art method and devices.